package org.hot100.h056;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: wjy
 * @Date: 2021/12/24 14:39
 */
public class Solution {

    /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
     *
     * 示例 1：
     *
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * 示例2：
     *
     * 输入：intervals = [[1,4],[4,5]]
     * 输出：[[1,5]]
     * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
     *
     * @param args
     */
    public static void main(String[] args) {

        int[][] ints = {{1, 3}, {2, 6}, {8, 10}, {10, 18}};

        Solution solution = new Solution();
        solution.merge4(ints);

    }

    /*public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();

        // 二维数组排序！！！
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int start = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= end) {
                end = Math.max(end, intervals[i][1]);
            } else {
                list.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }

        }
        list.add(new int[]{start, end});

        int[][] res = new int[list.size()][2];
        for (int i = 0; i < res.length; i++){
            res[i] = list.get(i);
        }
        return res;

    }*/

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0 || intervals.length == 1) {
            return intervals;
        }

        // 先将 intervals 进行排序
        Arrays.sort(intervals, (a1, a2) -> a1[0] - a2[0]);

        // 用于存放结果
        List<int[]> list = new ArrayList<>();

        // 变量 start 记录区间的第一个值，变量 end 记录区间的最后一个值
        int start = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {

            // 将二维数组下一行的第一个值与 上一行的最后一个值进行比较，如果小于等于 end 则进入 if
            if (intervals[i][0] <= end) {

                // end 大于 i 行的第一个值，但是不一定大于 第二个值
                end = Math.max(end, intervals[i][1]);
            } else {

                // i 行的第一个值大于 i-1 行的最后一个值，此时进入 else 将上一步的 start，end 的值存入 list
                list.add(new int[]{start, end});

                // 将 start，end 赋予新值
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }

        // 最后的 start，end
        list.add(new int[]{start, end});
        System.out.println(list);

        int[][] res = new int[list.size()][2];

        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }

    public int[][] merge2(int[][] intervals) {

        Arrays.sort(intervals, (a1, a2) -> a1[0] - a2[0]);

        List<int[]> lists = new ArrayList<>();

        int begin = intervals[0][0], end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
            } else {
                lists.add(new int[]{begin, end});
                begin = intervals[i][0];
                end = intervals[i][1];
            }
        }
        lists.add(new int[]{begin, end});

        for (int[] ints : lists) {
            System.out.println(ints[0] + "-------------" + ints[1]);
        }

        return null;
    }

    public int[][] merge3(int[][] intervals) {
        Arrays.sort(intervals, (a1, a2) -> a1[0] - a2[0]);
        int[][] ints = new int[intervals.length][intervals[0].length];
        int start = intervals[0][0], end = intervals[0][1];
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
            } else {
                lists.add(Arrays.asList(start, end));
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        lists.add(Arrays.asList(start, end));
        System.out.println(lists);
        return ints;
    }

    public int[][] merge4(int[][] intervals) {
        List<List<Integer>> lists = new ArrayList<>();
        int start = intervals[0][0], end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
            } else {
                lists.add(Arrays.asList(start, end));
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }

        lists.add(Arrays.asList(start, end));
        System.out.println(lists);
        return new int[0][0];
    }

}
